package club.xiaojiawei.back;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/21/22 1:44 PM
 * @question 131. 分割回文串
 * @description 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 * 回文串 是正着读和反着读都一样的字符串。
 */
public class Partition131 {

    public static void main(String[] args) {
        char[] chars = new char[]{'h', 'e', 'l', 'o'};
        System.out.println(new String(Arrays.copyOfRange(chars, 0, 2)));
        Partition131 test = new Partition131();
        List<List<String>> result = test.partition2("abccabba");
        System.out.println(result);
    }

    List<List<String>> result = new ArrayList<>();

    List<String> temp = new ArrayList<>();

    /**
     * 递归回溯
     * @param s
     * @return
     */
    public List<List<String>> partition(String s) {
        recursion(s, 0);
        return result;
    }

    public void recursion(String s, int startIndex){
        if (startIndex == s.length()){
            return;
        }
        boolean flag;
        for (int i = startIndex + 1; i <= s.length(); i++){
            String substring = s.substring(startIndex, i);
            flag = false;
            for (int f = 0, r = substring.length() - 1; f < r; f++, r--){
                if (substring.charAt(f) != substring.charAt(r)){
                    flag = true;
                    break;
                }
            }
            if (flag){
                continue;
            }
            temp.add(substring);
            if (i == s.length()){
                result.add(new ArrayList<>(temp));
                temp.remove(temp.size() - 1);
                return;
            }
            recursion(s, i);
            temp.remove(temp.size() - 1);
        }
    }

    /**
     * 递归(优化)
     * @param s
     * @return
     */
    public List<List<String>> partition2(String s) {
        recursion2(s.toCharArray(), 0);
        return result;
    }

    public void recursion2(char[] chars, int startIndex){
        if (startIndex == chars.length){
            return;
        }
        boolean flag;
        for (int i = startIndex; i < chars.length; i++){
            flag = false;
            for (int f = startIndex, r = i; f < r; f++, r--){
                if (chars[f] != chars[r]){
                    flag = true;
                    break;
                }
            }
            if (flag){
                continue;
            }
            temp.add(new String(Arrays.copyOfRange(chars, startIndex, i + 1)));
            if (i == chars.length - 1){
                result.add(new ArrayList<>(temp));
                temp.remove(temp.size() - 1);
                return;
            }
            recursion2(chars, i + 1);
            temp.remove(temp.size() - 1);
        }
    }

    boolean[][] f;
    List<List<String>> ret = new ArrayList<List<String>>();
    List<String> ans = new ArrayList<String>();
    int n;

    /**
     * 官方-回溯 + 动态规划预处理
     * 动态规划预处理提前建立回文表
     * 时间复杂度：O(n * 2^n)
     * 空间复杂度：O(n^2)
     * @param s
     * @return
     */
    public List<List<String>> partition3(String s) {
        n = s.length();
        f = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(f[i], true);
        }
//        动态规划预处理
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                f[i][j] = (s.charAt(i) == s.charAt(j)) && f[i + 1][j - 1];
            }
        }

        dfs(s, 0);
        return ret;
    }

    public void dfs(String s, int i) {
        if (i == n) {
            ret.add(new ArrayList<String>(ans));
            return;
        }
        for (int j = i; j < n; ++j) {
            if (f[i][j]) {
                ans.add(s.substring(i, j + 1));
                dfs(s, j + 1);
                ans.remove(ans.size() - 1);
            }
        }
    }

    /**
     * 回溯 + 记忆化搜索
     * 在递归的同时建立回文表
     * 时间复杂度：O(n * 2^n)
     * *空间复杂度：O(n^2)
     * @param s
     * @return
     */
    public List<List<String>> partition4(String s) {
        n = s.length();
        t = new int[n][n];
        dfs2(s, 0);
        return ret;
    }

    int[][] t;
    public void dfs2(String s, int i) {
        if (i == n) {
            ret.add(new ArrayList<String>(ans));
            return;
        }
        for (int j = i; j < n; ++j) {
            if (isPalindrome(s, i, j) == 1) {
                ans.add(s.substring(i, j + 1));
                dfs2(s, j + 1);
                ans.remove(ans.size() - 1);
            }
        }
    }

    // 记忆化搜索中，f[i][j] = 0 表示未搜索，1 表示是回文串，-1 表示不是回文串
    public int isPalindrome(String s, int i, int j) {
        if (t[i][j] != 0) {
            return t[i][j];
        }
        if (i >= j) {
            t[i][j] = 1;
        } else if (s.charAt(i) == s.charAt(j)) {
            t[i][j] = isPalindrome(s, i + 1, j - 1);
        } else {
            t[i][j] = -1;
        }
        return t[i][j];
    }

    String[][] ps;
    ArrayList<String> path = new ArrayList<>();

    /**
     * 民间-回溯 + 动态规划预处理
     * @param s
     * @return
     */
    public List<List<String>> partition5(String s) {
        int n = s.length();
        ps = new String[n][n];
        initP(s.toCharArray());
        dfs(n, 0);
        return result;
    }

    private void dfs(int n, int i) {
        if (i == n) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int j = 1; j <= n - i; j++) {
            if (ps[i][i + j - 1] != null) {
                path.add(ps[i][i + j - 1]);
                dfs(n, i + j);
                path.remove(path.size()-1);
            }
        }
    }

    private void initP(char[] s) {
        int len = s.length;
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (s[i] == s[j] && (j - i < 2 || ps[i + 1][j - 1] != null)) {
                    ps[i][j] = new String(Arrays.copyOfRange(s, i, j + 1));
                }
            }
        }
    }

}
